//
//  53_最大子数组和.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/3/4.
//

import UIKit
/**
 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

 子数组
 是数组中的一个连续部分。
 示例 1：

 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
 输出：6
 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
 示例 2：

 输入：nums = [1]
 输出：1
 示例 3：

 输入：nums = [5,4,-1,7,8]
 输出：23
 */
class GetMaxSubArray {
    static func QA() {
        let tem = GetMaxSubArray()
        let result = tem.maxSubArray([-2,1,-3,4,-1,2,1,-5,4]);
        print("******", result)
    }
//    1、遍历所有的情况获取最大值
    func maxSubArray(_ nums: [Int]) -> Int {
        if nums.count == 1 {
            return nums[0]
        }
        var maxCount = nums[0]
        for begin in 0..<nums.count {
            var sum = 0
            for end in begin..<nums.count {
                sum = sum + nums[end]
                maxCount = max(maxCount, sum)
            }
        }
        return maxCount
    }
}

/// 优化1(分治)
class GetMaxSubArray_S {
    static func QA() {
        let tem = GetMaxSubArray_S()
        let result = tem.maxSubArray([-2,-1,-3]);
        print("1******", result)
    }
    func maxSubArray(_ nums: [Int]) -> Int {
        if nums.count == 1 {
            return nums[0]
        }
        return getBeginRangEndMax(nums, begin: 0, end: nums.count)
    }
    
    /// 获取begin 到 end 的最值【begin end)
    /// - Parameters:
    ///   - nums: 数组
    ///   - begin: 开始
    ///   - end: 结束
    /// - Returns: 结果
    func getBeginRangEndMax(_ nums: [Int], begin: Int, end: Int) -> Int {
        if end - begin < 2 {
            return  nums[begin]
        }
        
        let mid = (begin + end) >> 1
        let leftMax = getBeginRangEndMax(nums, begin: begin, end: mid)
        let rightMax = getBeginRangEndMax(nums, begin: mid, end: end)
        let getMax = max(max(leftMax, rightMax), getRang(begin, end, nums))
        
        return getMax
    }
    
    func getRang(_ begin: Int, _ end: Int, _ nums: [Int]) -> Int {
        let mid = (begin + end) >> 1

        var leftMax = nums[mid-1]
        var leftSum = 0
        for i in (begin..<mid).reversed() {
            leftSum = leftSum + nums[i]
            leftMax = max(leftMax, leftSum)
        }
        var rightMax = nums[mid]
        var rightSum = 0
        for i in (mid..<end) {
            rightSum = rightSum + nums[i]
            rightMax = max(rightSum, rightMax)
        }
        return leftMax + rightMax
    }
}
